package algo;

import util.RandomArray;
import java.util.Arrays;

/**
 * Created by pc on 2015/1/18.
 * 从左往右
 * 扫描出最小的数放在最左边，然后向右继续重复扫描
 * 需要记住最小值的下标, 
 * 相比冒泡排序减少交换的次数到N，但是比较次数仍然为n*(n-1)*
 */
public class SelectionSort {
    public static void sort(int[] arr) {
        int min, minPos = 0;
        for (int pos = 0; pos < arr.length; pos++) {
            //整齐后右边第一位为最小数的初始值
            min = arr[pos];
            for (int i = pos + 1; i < arr.length; i++) {
                if (arr[i] < min) {
                    //修改最小值并记住其位置
                    min = arr[i];
                    minPos = i;
                }
            }
            //扫描完成后交换扫描范围的最小值位置
            arr[minPos] = arr[pos];
            arr[pos] = min;
        }
    }

    public static void main(String[] args) {
//        int [] testArr = new int[] {45, 23, 12, 1, 34};
        int[] testArr = RandomArray.getRandomIntArray(10);

        System.out.println("before sort: " + Arrays.toString(testArr));
        SelectionSort.sort(testArr);
        System.out.println("after sort: " + Arrays.toString(testArr));

    }
}
